package com.hot100;

public class h105 {
    int[] preorder;
    int[] inorder;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        this.inorder = inorder;
        return dfs(0,preorder.length-1,true);
    }
    public TreeNode dfs(int left,int right,boolean flag){
        if (left > right) return null;
        if (left == preorder.length ) return null;
        TreeNode node = new TreeNode(preorder[left]);
        int Leftcount = 0;
        int i = flag ? 0 : left;
        for (;i  < right; i++){
            if (inorder[i] == preorder[left]){
                break;
            }
            Leftcount++;
        }
        node.left = dfs(left + 1,left + Leftcount,true);
        node.right = dfs(left + Leftcount + 1, right,false);
        return node;
    }
}



















class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }